package leetcode.剑指offer.前40;

import org.junit.Test;

/**
 * @author :songyaozhang
 * @date :Created 2021/7/22 15:21
 * @description :
 */
public class 剑指_10_I_斐波那契数列 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.fib(45));
    }

    class Solution {
        //1 1 2 3 5 8
        public int fib(int n) {
            if (n == 0) return 0;
            if (n <= 2) return 1;
            final int MOD = 1000000007;
            int a = 1;
            int b = 1;
            for (int i = 2; i < n; i++) {
                int c = (a + b) % MOD;
                a = b;
                b = c;
            }
            return b;
        }
    }

}
